package 差分Plus离散化;

import org.junit.Test;

import java.util.Arrays;

/**
 * @author aodre , QQ : 480029069
 * @date 2023/5/28 9:28
 */
public class lc2251花期内花的数目 {


    /*
    先解释 一下 ， 排序 + 二分的 一个 算法：
    ①:先找到 st <= pt 的所有 花期 在 pt 之前的 花的 数目 (这是 pt 所能看到的 ** 可能的最大的花期数目 **) 记为 x
    因为  st 和 et 是 成对 出现的  且 st <= et , 所以 只需要 在 找出 et < pt 的 的花期数目,(这个是 在pt 之前就已经 凋谢的花, 看不到) 记为 y
    而且 必然  有  x >= y 的存在, (因为是成对 出现的 ,而且 这里有点小绕! )
    所以  x - y  就是 pt 能看到的花期的数目
     */
    public int[] fullBloomFlowers(int[][] flowers, int[] people) {
        int pLen = people.length;
        int fLen = flowers.length;
        int ans[] = new int[pLen];
        int st[] = new int[fLen];
        int et[] = new int[fLen];
        for (int i = 0; i < fLen; i++) {
            st[i] = flowers[i][0];
            et[i] = flowers[i][1];
        }
        // 对et 和 st 进行 排序, 为了 进行二分
        Arrays.sort(et);
        Arrays.sort(st);
        for(int i = 0;i < pLen;i++){
            int x = binaryRight(people[i],st);
            int y = binaryRight(people[i] - 1, et);  // 求 et < pt  等价于  et <= pt - 1
            ans[i] = x - y;
        }
        return ans;
    }

    // 写一个 二分  <= x 的最右边
    /*
     这里的二分 优化, 是 get 到的 一个  补充的知识点!
     */
    public int binaryRight(int aim, int nums[]) {
//        int index = -1;
        int l = 0, r = nums.length - 1;
        while (l < r) {
            int mid = l + r + 1 >> 1;
            if(nums[mid] > aim){
                r = mid - 1;
            }else{
//                index = l;
                l = mid;
            }
        }
        if(l == 0){
            return nums[l] <= aim ? l + 1 : 0;
        }
        return l + 1;
//        return index;
    }


    @Test
    public void test(){
        int f[][] = {{1,6},{3,7},{9,12},{4,13}};
        int per[]	 = {2,3,7,11};
        int[] ints = fullBloomFlowers(f, per);
        String s = Arrays.toString(ints);
        System.out.println(s);
    }
}
